一个比较好写的小常数 $O(n)-O(1)$ RMQ 做法,巧妙运用了分块与位运算函数.
RMQ 问题:给出一个长度为 $n$ 的整数数列 $a$ ,有 $m$ 次询问,每次询问一个区间 $[l,r]$ 内 $a_i$ 的最小值.
一些常见的做法:
- 线段树, $O(n)-O(\log n)$ .
- 朴素的 ST 表, $O(n\log n)-O(1)$ .
- RMQ 转 LCA, 离线后用 tarjan 算法求 LCA, $O(n\alpha(n))-O(1)$ .
- RMQ 转 LCA, 然后用 $\pm1$ RMQ 做法解决, $O(n)-O(1)$ .
这里介绍另外一种基于位运算的 $O(n)-O(1)$ 做法,相比上面的最后一种做法更为好写,且常数较小.
下面的做法需要先保证机器字节长 $w\ge \log n$ ,这在我们平常遇到的问题中绝大多数时候都是成立的.
考虑将序列分块,每块大小为 $\Theta(\log n)$ ,预处理整块部分的 ST 表,这里对 $O(\frac n {\log n})$ 个数建 ST 表,时间复杂度 $O(n)$ .
实现时候可以取块大小为 $\frac 3 2\log n$ ,常数较为优秀.
若询问的端点 $l,r$ 来自两个不同的块,整块可以在 ST 表上询问,边角是块的前缀 / 后缀最小值,这可以 $O(n)$ 预处理.
难点是 $l,r$ 位于同一个块中的情况,我们在预处理时,对每个块从左到右维护一个单调栈,满足元素从栈底到栈顶单调上升,那么 $[l,r]$ 的最小值所在的位置,就是加入 $r$ 后单调栈中从底部到顶部第一个 $\ge l$ 的位置.
每加入一个元素时,我们就将当前栈的形态给存储下来,由于每块大小是 $O (\log n)$ 的,而 $w\ge\log n$ ,所以栈的形态可以压缩到一个二进制数中,假定块的左端点为 $S$ ,则这个数的第 $i$ 个二进制位表示了 $S+i$ 这个位置是否在单调栈中.
那么查询单调栈中从底部到顶部第一个 $\ge l$ 的位置,就可以转化为问这个二进制数从第 $l$ 位往前第一个为 $1$ 的位置.
我们可以利用 __builtin_ctz 函数 $O(1)$ 计算,记所询问的单调栈转化为二进制数表示为 $x$ .
调用__builtin_ctz(x) 会返回 $x$ 二进制下末尾 $0$ 的个数 ,那么显然 l + __builtin_ctz(x >> l) 即为所求.
这份代码 实现了上述做法 ,目前在 Loj 和 Luogu 上都是效率 rk1 ,RMQ 部分的代码只有不到 2k .